\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
\usepackage{color}
%\usepackage{algorithmic}
\usepackage{amssymb}
%\usepackage{listings}
\usepackage{graphicx} % para insertar imagenes
\usepackage{amsthm} % para proof
%\usepackage{natbib} % para citar
\usepackage{url}
\definecolor{lnk}{rgb}{0,0,0.4}
\usepackage[colorlinks=true,linkcolor=lnk,citecolor=blue,urlcolor=blue]{hyperref}

\newcommand{\func}[2]{\texttt{#1}(#2)\\}
\newcommand{\tab}{\hspace*{2em}}
\newcommand{\FOR}{\textbf{for }}
\newcommand{\TO}{\textbf{ to }}
\newcommand{\IF}{\textbf{if }}
\newcommand{\WHILE}{\textbf{while }}
\newcommand{\THEN}{\textbf{then }}
\newcommand{\ELSE}{\textbf{else }}
\newcommand{\RET}{\textbf{return }}
\newcommand{\MOD}{\textbf{ \% }}
\newcommand{\OR}{\textbf{ or }}
\newcommand{\tOde}[1]{\tab \small{O($#1$)}}
\newcommand{\Ode}[1]{O($#1$)}
\newcommand{\Omegade}[1]{\small{$\Omega$($#1$)}}
\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}
\newenvironment{pseudo}{\begin{tabular}{ll}}{\end{tabular}\VSP}

\newcommand{\gra}[1]{\noindent\includegraphics[scale=.60]{#1}\\}


\title{{\sc\normalsize Algoritmos y estructuras de datos III}\\{\bf Trabajo Práctico Nº1}}
\author{\begin{tabular}{lcr}Carla Livorno & 424/08 & carlalivorno@hotmail.com\\Thomas Fischer & 489/08 & tfischer@dc.uba.ar\\Kevin Allekotte & 490/08 & kevinalle@gmail.com \end{tabular}}
\date{\VSP \normalsize{Septiembre 2009}}
%\date{}
\begin{document}
\begin{titlepage}
\maketitle
\end{titlepage}
\tableofcontents
\newpage

	\begin{section}*{Introducción}	\addcontentsline{toc}{section}{Introducción}
	Este trabajo tiene como objetivo la aplicación de diferentes técnicas algorítmicas para la resolución de tres problemas particulares, el cálculo de complejidad teórica en el peor caso de cada algoritmo implementado, y la posterior verificación empírica.
	
	El lenguaje utilizado para implementar los algoritmos de todos los problemas fue C/C++
	
	\end{section}
	\begin{section}{Problema 1}
		\textit{Sea $v = (v_1 , v_2 , ... , v_n )$ un vector de números racionales. Determinar la menor cantidad posible de intervalos unitarios tales que cada elemento de $v$ pertenece al menos a uno de esos intervalos.}
		\begin{subsection}{Explicación}
		Ordenamos el vector $v$ en orden creciente con un algoritmo de merge-sort, para luego aplicar un algortimo goloso. Una vez ordenado podemos recorrer secuencialmente el vector ubicando intervalos unitarios que abarquen la mayor cantidad de elementos posibles. De esta forma se obtiene la menor cantidad de intervalos unitarios posibles.\Pa

		Tomamos el primer elemento del vector ordenado como el elemento minimo de uno de los intervalos. Iteramos sobre el vector hasta encontrar un elemento que no pertenezca al intervalo. Tomamos este elemento como el inicio de un nuevo intervalo, y seguimos iterando llevando la cuenta de los intervalos.

			\begin{subsubsection}{Análisis de complejidad}
				Elegimos el modelo uniforme para analizar la complejidad de este algoritmo porque el tamaño de los elementos es acotado y por lo tanto todas las operaciones elementales son de tiempo constante.
				
				Sea $n$ la longitud de $v$.\\
				
				
				\begin{pseudo}
					\func{intervalos}{$v$}
					\tab $merge\_sort(v)$ & \tOde{n log(n)}\\
					\tab $count \gets 0$\\
					\tab $min \gets -\infty$\\
					\tab \FOR $i\gets 0 \TO long(v)$ & \tOde{n}\\
					\tab\tab \IF $v[i] > min+1$ \THEN \\
					\tab\tab\tab $count \gets count+1$\\
					\tab\tab\tab $min \gets v[i]$\\
					\tab \RET $count$\\
				\end{pseudo}
				
				El merge sort divide el arreglo en 2 mitades (\Ode{1}), ordena recursivamente cada una $(2*T(n/2))$, y las fusiona sobre el arreglo original (\Ode{n}). Entonces la complejidad es $T(n)=2*T(n/2)+O(n)$, que por Teorema Maestro es \Ode{n log(n)}.
				
				Entonces la comlejidad del algoritmo \texttt{intervalos} es $O(n log(n) + n) = O(n log(n))$. Como los elementos del vector son de tamaño acotado, el tamaño de la entrada es proporcional a la longitud del vector ($n$). Entonces la complejidad del algoritmo es \Ode{t log(t)} donde $t$ es el tamaño de la entrada.
			\end{subsubsection}

		\end{subsection}
	
		\begin{subsection}{Pruebas y Resultados}

			Las entradas utilizadas para probar correctitud están en el archivo \texttt{pruebas.in}. Elegimos casos bordes como el vector de longitud cero, vectores ordenados y en orden inverso ya que también hay que verificar correctitud del merge-sort. Elegimos números reales muy cercanos y muy lejanos entre sí, también probamos con vectores de diversos tamaños.

			Para medir tiempos y contar operaciones generamos vectores de tamaños entre 1 y 100000 con elementos aleatorios.

			\gra{ej1_counts.png}
			\gra{ej1_times.png}

			En los graficos podemos observar que el tiempo de ejecución no solo es \Ode{n log(n)} en el peor caso, sino que siempre parece tardar lo mismo.
			Esto se debe a que el merge-sort se ejecuta en \Omegade{n log(n)}, y el barrido posterior sobre el vector siempre es hasta el final del mismo.

			Los resultados obtenidos se corresponden con el analisis teórico que esta representado por la línea verde en los graficos. 
			Vemos que la cantidad de operaciones / tiempo de ejecución (marcas rojas) se mantiene cada vez mas abajo de la misma.

			Por lo que seria lógico creer que tambien lo va a hacer para mayores tamaños de entrada que los aquí representados.

		\end{subsection}
	\end{section}
	
	
	
	
	
	
	
	
	
	\begin{section}{Problema 2}
		\textit{Dado $n$ $\in$ $\mathbb{N}$, encontrar uno de sus amigos, en caso de que exista}
		\begin{subsection}{Explicación}
			Para calcular la suma de los divisores propios del número, buscamos todos los factores primos y luego aplicamos la formula:
			$$\prod_{p \in factores(n)}{\frac{p^{m_p+1}-1}{p-1}}-n$$ donde $m_p$ es la multiplicidad de p en n.
			Para una idea de la demostración de la formula, ver el apéndice A.\Pa

			Sea $a$ la suma de los divisores propios de $n$. El número amigo de $n$ existe sii la suma de los divisores propios de $a$ es igual a $n$ (y $a \neq n$). Si existe, el amigo de $n$ es $a$.\Pa
			
			Para factorizar un número $n$ buscamos el menor primo que lo divide, $p$. Dividimos sucesivamente $n$ por $p$ mientras $p$ sea divisor, contando la cantidad de divisiones (multiplicidad de $p$ en $n$).\Pa
			
			Para encontrar el menor primo que divide a un número $n$ recorremos linealmente los numeros menores a $\sqrt{n}$ probando si es divisor.\\ (el menor número que lo divide es siempre primo, y si ninguno menor que $\sqrt{n}$ lo divide entonces $n$ es primo).\Pa

			\begin{subsubsection}*{Análisis de complejidad} \addcontentsline{toc}{subsubsection}{Análisis de complejidad}
			
			%Elegimos el modelo uniforme porque consideramos que las operaciones entre números son de tipo constante que es lo más parecido a la realidad porque trabajamos con 
			%números de tamaño constante (\texttt{unsigned long long int}).

			Esta vez, elegimos un modelo logarítmico para analizar el algoritmo, ya que las operaciones que aplicamos, 
			en teoría, dependen del logaritmo del número en cuestión, o dicho de otra forma, del tamaño de la entrada.
			No obstante, en los resultados muchas de ellas tienen costo uniforme por trabajar con números de tamaño acotado (\texttt{unsigned long long int}) para simplificar la implementación.

			Por esto tambien analizamos un poco la complejidad obtenida bajo el modelo uniforme. \\

				\begin{pseudo}
					\func{Factorizar}{$n$}
					\tab \WHILE $n>1$ \\
					\tab\tab $p \gets menorPrimoDivisor(n)$ & \tOde{\sqrt{n}*{log}^{2}(n)}\\
					\tab\tab \WHILE $p$ divide a $n$ & \tOde{{log}^{2}(n)}\\
					\tab\tab\tab $n \gets n/p$ & \tOde{{log}^{2}(n)}\\
				\end{pseudo}

				
				\begin{pseudo}
					\func{menorPrimoDivisor}{$n$}
					\tab $m \gets 2$ \\
					\tab \WHILE $m \leq \sqrt{n}$ & \tOde{log(m)} \\
					\tab\tab \IF $m$ divide a $n$ \THEN \RET $m$ & \tOde{{log}^{2}(n)} \\
					\tab\tab $m \gets m+1$ & \tOde{log(m)} \\
					\tab \RET $n$
				\end{pseudo}
				
				El primer \WHILE de \texttt{Factorizar} se ejecuta \Ode{log(n)} veces, porque en cada iteración se divide a $n$ por al menos un primo divisor.
				
				Como la cantidad de primos divisores de un número es menor o igual a $log(n)$ (porque $n=\prod_{p\in factores(n)}{p^{m_p}}$) el ciclo se ejecuta a lo sumo $log(n)$ veces.\Pa
				
				El segundo \WHILE de \texttt{Factorizar} también se ejecuta \Ode{log(n)} veces, porque se divide sucesivamente a $n$ por $p$ y la cantidad de veces que un primo divide a $n$ es menor o igual a $log(n)$. (porque la multiplicidad de un factor es $\leq log(n)$).\Pa

				El \WHILE de \texttt{menorPrimoDivisor} se ejecuta a lo sumo $\sqrt{n}$ veces. Luego, la complejidad de \texttt{menorPrimoDivisor} es \Ode{\sqrt{n}*( {log}^{2}(n) + 2log(m) )} = \Ode{\sqrt{n}*{log}^{2}(n)}. \Pa

			\end{subsubsection}

			\begin{subsubsection}{modelo logarítmico}

				\noindent Luego, la complejidad del algoritmo completo bajo el modelo logarítmico resulta ser:
				$$ O( log(n) * ( \sqrt(n)*{log}^{2}(n) + log(n)*2{log}^{2}(n) ) ) = O( \sqrt(n){log}^{3}(n) + {log}^{4}(n) ) = O( \sqrt(n){log}^{3}(n) )$$
				$log(n) \in O(\sqrt{n})$ porque 
				$$\lim_{n\rightarrow\infty}{\frac{log(n)}{\sqrt{n}}}=_{L'Hopit} \lim_{n\rightarrow\infty}{\frac{n^{-1}}{\frac{n^{-\frac{1}{2}}}{2}}} = \lim_{n\rightarrow\infty}{\frac{2}{\sqrt{n}}} = 0$$

				\noindent Esta complejidad es estrictamente mejor que lineal ya que 
				$$ \sqrt(n){log}^{3}(n) < {\sqrt{n}}^{2} = O(n)$$
				porque
				$$ \lim_{n\rightarrow\infty}{\frac{{log}^{3}(n)}{\sqrt(n)}} = 0$$

			\end{subsubsection}

			\begin{subsubsection}{modelo uniforme}

				\noindent La complejidad del algoritmo en modelo uniforme (tomando todas las operaciones entre numeros constantes) es: 
				$$O(log(n) (\sqrt{n}+log(n))) \subset O(\sqrt{n}log(n)+log^2(n)) \subset O(\sqrt{n}log(n)+\sqrt{n}log(n)) \subset O(\sqrt{n}log(n))$$
				%que es estrictamente mejor que lineal porque $$O(\sqrt{n}log(n)) < O(\sqrt{n}^2) \subset O(n)$$

			\end{subsubsection}

			\begin{subsubsection}{en funcion del tamaño de entrada}

				El tamaño de la entrada es $log(n)$. ($n=2^t$)
				Entonces la complejidad de este algoritmo en funcion del mismo es: $O(\sqrt{2^t}+{log(2^t)}^{3}) \subset O(2^{\frac{t}{2}}+{t}^{3}) \subset O(2^{\frac{t}{2}})$ donde $t$ es el tamaño de la entrada.\Pa

			\end{subsubsection}

		\end{subsection}
		
		\begin{subsection}{Pruebas y Resultados}
			Las entradas utilizadas para probar correctitud están en los archivos \texttt{pruebas\_amigos.in}, \texttt{pruebas\_primos.in} y \texttt{pruebas\_otros.in}. Elegimos como entrada números que tienen amigo (incluyendo los que su amigo es si mismo), números que no tienen amigo, números primos, etc para probar el comportamiento del algoritmo en sus distintas variantes.

			Para medir tiempos y cantidad de operaciones generamos números aleatorios entre $1$ y $10^9$, distinguiendo a los primos de los demás observarlos por separado (porque son el peor caso).

			\gra{ej2_counts.png}
			\gra{ej2_times.png}
			\gra{ej2_counts_exp.png}
			
			\newpage

		Observando los graficos notamos que para números de tamaño de entrada similar hay una diferencia notable entre los primos y no-primos tanto en la cantidad de operaciones como en el tiempo de ejecución.\\

		En general, vemos que el algoritmo se comporta como \Omegade{\sqrt(n)} para los numeros primos, ya que lo único que suma en este caso es el tiempo que tarda en darse cuenta 
		que el número es primo (encontrar sus divisores).

		 Dado que el algoritmo recorre linealmente los divisores del número original hasta llegar a la raíz del mismo, se justifica la complejidad observada.\\

		En pocos lugares notamos algunos outlayers no-primos que tardan mas que los primos. Estos son números que tienen muchos divisores, 
		y donde además el numero resultante de la suma de los mismos es o bien primo, o también tiene un gran número de divisores.

		Como vemos, los resultados prácticos se mantienen cada vez mas abajo de la complejidad teórica analizada (línea azul) y se corresponden en forma con la misma.
		Por esto suponemos que es una buena cota para la complejidad del algoritmo.
		
		\end{subsection}
	\end{section}
	
	
	
	
	
	
	
	
	
	
	
	\begin{section}{Problema 3}
		\textit{		\textit{Se tiene un tablero de $n$ filas y $n$ columnas formado por casillas cuadradas. [...] .Determinar la cantidad de formas de cubrir exclusivamente las casillas sanas del tablero, utilizando las fichas de dominó.}}
		\begin{subsection}{Explicación}
			El Algotirmo busca todas las formas de llenar el tablero utilizando la técnica de backtracking. Para esto, el algoritmo recorre la matriz poniendo las fichas en las posiciones sanas desocupadas hasta que: \begin{itemize} 	\item llena el tablero (encuentra una combinación posible), o \item no puede completar el tablero de esa forma \end{itemize}
			
			Luego saca la última ficha que puso y vuelve a intentar llenar el tablero poniendo esta ficha de otra forma. Termina cuando encuentra todas las soluciones.\\
			
			Además, el algoritmo utiliza algunas propiedades del tablero para ser más eficiente:
			
			\begin{subsubsection}{Optimizaciones}
			Decimos que $(i,j)$ es una casilla blanca si $i\%2=j\%2$ (tienen la misma paridad), y es negra en caso contrario (Como un tablero de ajedrez).
			
			Una ficha de dominó ocupa siempre una casilla de cada color (porque todas las casillas adyacentes son de distinto color). Esto implica que un tablero con distinta cantidad de casillas negras que blancas no tiene solución.\\
			
			
			Si el tablero está completamente sano podemos aplicar la siguiente propiedad para calcular la cantidad de combinaciones:
			
			\textit{Sea el tablero sano de tamaño $n \times m$. La cantidad de formas de llenarlo usando fichas de dominó está dada por \footnote[0]{ \url{http://en.wikipedia.org/wiki/Domino_tiling} }:}
			$$ \prod_{j=1}^m \prod_{k=1}^n \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )^{1/4} $$

			La cantidad de combinaciones de 2 tableros independientes se puede calcular como el producto de las combinaciones de cada uno.
			
			Nuestro algoritmo detecta regiones sanas independientes (regiones separadas entre sí por casillas rotas). Para cada región verifica que pueda tener solución (con la optimización de los colores) y luego (si todas tienen solución) aplica el algoritmo para cada región independientemente y calcula el producto.
			\end{subsubsection}
			
			\begin{subsubsection}{Análisis de complejidad}

				Elegimos el modelo uniforme porque consideramos que las operaciones elementales son constantes porque todos los valores son acotados.\\
				La complejidad de este algoritmo es exponencial.\Pa

				El peor caso para el algoritmo es aplicar el backtracking sobre el tablero entero. La complejidad del backtracking $(T(n))$ se puede acotar por $2*T(n-1) + O(1)$, porque para cada casillero del tablero se puede poner una ficha en posicion horizontal o vertical y por cada posicion se calculan las combinaciones de las casillas siguientes.
				$T(n) \in O(2^n)$ porque $2^n \in O(2*(2^{n-1}) + 1)$
				
				Como en el peor caso nuestro algoritmo hace backtracking sobre los $n^2$ casilleros, la complejidad es $O(2^{n^2})$.

				El tamaño de la entrada es $n^2$. Entonces la complejidad del algoritmo es $O(2^{t})$ donde $t$ es el tamaño de la entrada.
			\end{subsubsection}
		\end{subsection}
		
		\begin{subsection}{Detalles de la implementación}
			\begin{pseudo}
				\func{cantCombinaciones}{$tablero$}
				\IF $cantBlancasSanas \neq cantNegrasSanas$ \OR todoRoto \THEN \RET 0\\
				\ELSE \IF $cantBlancasSanas + cantNegrasSanas = n^2$ \THEN \RET $\texttt{todoSano}(n,n)$\\
				\ELSE \\
				\tab $R \gets \texttt{regionesSeparadas}(tablero)$\\
				\tab \IF $\texttt{algunaNoTieneSolucion}(R)$ \THEN \RET 0\\
				\tab \ELSE \\
				\tab\tab $prod \gets 1$\\
				\tab\tab \FOR $region \in R$\\
				\tab\tab\tab $prod \gets prod*\texttt{contar}(region)$\\
				\tab\tab \RET $prod$
			\end{pseudo}

			\begin{pseudo}
				\func{contar}{$region$}
				\IF $\texttt{esRectanguloSano}(region)$ \THEN \RET $\texttt{todoSano}(altura(region),ancho(region))$\\
				\ELSE \RET $\texttt{backtrack}(region)$
			\end{pseudo}

			\begin{itemize} 
			\item \texttt{regionesSeparadas:} Para cada posición del tablero, si es sana y todavia no pertenece a una región corre un bfs buscando todas las posiciónes sanas adyacentes considerandolas de la misma región. Repite este paso sucesivamente hasta que cada posición sana del tablero tiene asignada una región. La complejidad es el tamaño del tablero porque a lo sumo recorre 2 veces cada casilla y la cantidad de vecinos de una casilla es constante (4).\\

			\item \texttt{algunaNoTieneSolucion:} Mientras busca regiones independientes, el algortimo verifica que las encontradas hasta el momento tengan solución. Si no es así termina y devuelve 0, ya que en última instancia el resultado final va a ser la productoria de los resultados parciales, y con que uno sea cero ya es suficiente para devolver cero.\\

			\item \texttt{esRectanguloSano:} Verifica si la región (casillas sanas) es un rectangulo para determinar a que función invocar. Si es rectangulo, calcula las combinaciones posibles de poner las fichas en esa region mediante $todo\_sano$ ya que la complejidad de dicha función es mucho mejor que la de backtracking. La complejidad es el tamaño de la región \Ode{\texttt{(maxx-minx)}\times\texttt{(maxy-miny)}}\\
	
			\item \texttt{todoSano:} Es el algoritmo que utiliza la fórmula mencionada arriba para determinar la cantidad de combinaciones de una región rectangular toda sana. La complejidad es \Ode{\texttt{alto}\times\texttt{ancho de la región} }\\
			\end{itemize} 
		
			
			El algoritmo de backtracking recorre los casilleros sanos. Para cada uno chequea si puede poner una ficha verticalmente, o en su defecto horizontalemte (Para colocar una ficha marca la posición como $H$ o $V$, y marca la casilla adyacente correspondiente como ocupada). Si en esa casilla no puede poner una ficha, comienza a retroceder.
			
			Cuando retrocede, recorre las casillas en orden inverso. Si encuentra una $H$ la saca y sigue retrocediendo. Si encuentra una $V$, chequea si en esa posicion puede poner una ficha horizontalmente. Si puede, pone una $H$ (marca ocupada la adyacente) y comienza a recorrer para adelante (de la forma mencionada arriba). Sino, saca la ficha $V$ y sigue retrocediendo.
			
			Avanzando, si llega al final del tablero encontró una solución. Incrementa el contaor de soluciones y comienza a retroceder.
			
			Retrocediendo, si llega al comienzo del tablero, termina y devuelve el contador de soluciones.
			
		\end{subsection}
	
		\begin{subsection}{Pruebas y Resultados}
			Las entradas utilizadas para probar correctitud estan en el archivo \texttt{pruebas.in}. Fueron elegidas para probar casos bordes y verificar la eficiente detección de tableros sin solución como tableros de la siguiente forma: "vacio", todo roto, con cantidad de casilleros impar, con distinta cantidad de casilleros blancos que negros, con cantidad de casilleros impar pero con una rota (cantidad casilleros sanos par), en este último caso si el casillero roto es del color del primer casillero tiene solución sino no, ya que hay un casillero más de ese color.
			
			Otras pruebas las elegimos para verificar la correctitud de algunas funciones particulares como un tablero dividido en regiones donde una no puede llenarse, tablero dividido en regiones que pueden llenarse (probamos con regiones rectangulares y no rectangulares).
			
			Y por último probamos entradas suficientemente grandes (de todo tipo: por regiones, todo sano, etc).

			Para analizar la complejidad temporal del algoritmo (tiempo y cantidad de operaciones) generamos para cada tamaño (entre 1 y 8) tableros aleatorios con distintas proporciones de casilleros sanos/rotos.
			
			\gra{ej3_counts.png}
			\gra{ej3_times.png}
			
			\newpage
			
			También creamos tableros que sabíamos que no tienen solución para analizar el comportamiento del algoritmo y observamos que tarda siempre un tiempo constante. Esto es gracias al chequeo de cantidad de casillas 'blancas' y 'negras' que hacemos al comienzo del algoritmo.
			
			\gra{ej3_counts_imposible.png}
			\gra{ej3_times_imposible.png}
			
			\newpage
			
			Para probar tanto la correctitud como el tiempo de ejecución de la optimización de \textbf{rectangulos sanos} generamos en el archivo \texttt{test\_sanos.in} muchos tableros de distintos tamaños que tienen la propiedad de estar formados por rectangulos independientes totalmente sanos, como por ejemplo:
			\begin{center}
			\gra{tablero_sano.png}
			\end{center}
			Como resultado comprobamos que el algoritmo puede resolver este tipo de tableros en tiempo \Ode{n^2}. Tiene sentido y concuerda con el resultado teórico porque para llegar a la solución tiene que recorrer todo el tablero, que tiene $n^2$ casillas.
			
			\gra{ej3_counts_sanos.png}
			
			
			\gra{ej3_times_sanos.png}
		\end{subsection}

	\end{section}
	
	\begin{section}{Compilación y ejecución de los programas}
		Para compilar los programas se puede usar el comando \texttt{make} (Requiere el compilador \texttt{g++}).
		Se pueden correr los programas de cada ejercicio ejecutando \texttt{./intervalos}, \texttt{./amigos} y \texttt{./domino} respectivamente.
		
		Los programas leen la entrada de stdin y escriben la respuesta en stdout. Para leer la entrada de un archivo \texttt{Tp1EjX.in} y escribir la respuesta en un archivo \texttt{Tp1EjX.out} ses puede usar:\\ \texttt{./(ejecutable) < Tp1EjX.in > Tp1EjX.out}
		
		Para medir los tiempos de ejecución: \texttt{./(ejecutable) time} y opcionalmente se pueden pasar argumentos que indican la cantidad de tiempo mínima de ejecución y la cantidad de mediciones para cada instancia. Por ejemplo: \texttt{./(ejecutable) time 0.5 3} toma 3 mediciones de cada instancia (separadas por espacios); ejecuta el algoritmo $n$ veces hasta que tarde al menos 0.5 segundos y divide el resultado por $n$ (el segundo parametro define la presición de la medición).
		
		Para contar la cantidad de operaciones: \texttt{./(ejecutable) count}. Devuelve la cantidad de operaciones de cada instancia.
		
		Para medir los tests de tiempo de ejecución y cantidad de operaciones se puede usar \texttt{make time} y \texttt{make count} respectivamente. Esto genera un archivo \texttt{time.dat} o \texttt{count.dat} que contiene las mediciones de cada instancia de prueba. Se pueden graficar estas mediciones con \texttt{make plot\_time} y \texttt{make plot\_count} (Requiere \texttt{gnuplot}).
	\end{section}
	
	\begin{section}{Conclusiones}
		Pudimos implementar las soluciones a los problemas propuestos utilizando diversas técnicas algorítmicas. En todos los casos las mediciones de tiempo y cantidad de operaciones se correspondieron con las complejidades teóricas calculadas. Esto indica que los modelos elegidos fueron adecuados. Observamos que los problemas 2 y 3 tienen complejidad exponencial, esto significa que no estan "bien" resueltos para tamaños de entrada suficientemente grandes.
	\end{section}

	\newpage

	\begin{section}*{Apéndice A} \addcontentsline{toc}{section}{Apéndice A}

		\label{demo} \noindent \textbf{teorema:} $ \sum_{d|n}{d} = \prod_{i=1}^{k} \frac{{{P}_{i}}^{{m}_{i}+1}-1}{{P}_{i}-1} $.

		\begin{proof}[Demostración (informal)]
		Sea $n$ el número de entrada. Podemos escribir la factorización de $n$ como 
		$$\prod_{i=1}^{k}{{{P}_{i}}^{{m}_{i}}}$$
		Sea $d$ un divisor de $n$, entonces los factores primos de $d$ deben ser los mismos que los de $n$ con una multiplicidad igual o menor. O sea la factorización de $d$ sería 
		$$\prod_{i=1}^{k}{{{P}_{i}}^{{\mu}_{i}}}, 0 \leq {\mu}_{i} \leq {m}_{i}$$
		Luego, podemos escribir a la suma de los divisores de $n$ como 
		$$\sum_{d|n}{d} = \sum_{{\mu}_{1}=0}^{{m}_{1}} \sum_{{\mu}_{2}=0}^{{m}_{2}}...\sum_{{\mu}_{k}=0}^{{m}_{k}} \prod_{i=i}^{k}{{{P}_{i}}^{{\mu}_{i}}} $$
		Esta suma de productos, puede ser reescrita como producto de sumas de la forma
		$$ \prod_{i=1}^{k} \sum_{{\mu}_{i}=0}^{{m}_{i}} {{P}_{i}}^{{\mu}_{i}} $$
		Como vemos que las sumas tienen la forma de series geométricas, podemos reemplazarlas por la fórmula para el término n-ésimo de una sucesión de este tipo y finalmente llegamos a la fórmula
		$$ \sum_{d|n}{d} = \prod_{i=1}^{k} \frac{{{P}_{i}}^{{m}_{i}+1}-1}{{P}_{i}-1} $$
		\end{proof}
	\end{section}

\end{document}

